A packet-based network includes multiple nodes that are coupled together to facilitate the forwarding of traffic from one node to some subset of the other nodes. Nodes that intelligently forward traffic between these nodes are often referred to as routers, bridges, or switches. In the case of routers, each router typically has a plurality of ports and maintains a routing table. Traffic is received on one of the ports in the form of a packet, which may be referred to in the alternative as, e.g., a segment, frame, cell, or datagram. Each packet typically includes a header, a payload, and a trailer. The header includes, e.g., a source Internet protocol (IP) address and a destination IP address. Source and destination IP addresses are typically 32 bits long and may be represented in decimal dot notation such that any one of the 4 parts of the notation have a decimal value of 0 to 255, e.g., 127.0.0.1. The payload is data that is encapsulated within the packet. The routing table is typically traversed with the goal of finding the longest prefix match between a key and a search value in the routing table. The key is typically information that is obtained from the header of the packet, such as the destination IP address. The routing table has a plurality of routing table entries, each of which have unique search values. In other words, a prefix of the key, which is a variable number of consecutive bits starting with the most significant bit, is matched to a same length prefix of a search value of a routing table entry such that the prefix is as long as possible. In the case of an exact match, the length of the prefix is the same as the length of the key. Routing information including, e.g., a port identifier, associated with the routing table entry with the longest matching prefix is used to forward the packet to the destination of the packet or an intermediate node that is (preferably) closer to the destination, sometimes referred to as a “next hop.” Often, routing tables are structured using radix tree techniques.
In a network that includes a plurality of logical networks, such as virtual private networks (VPNs), routing tables are typically maintained for each logical network. When routing tables are organized in radix tree structures, each logical network has a network specific radix tree. FIGS. 1A and 1B depict radix tree routing table diagrams 100A and 100B for logical networks 1 and 3, respectively. The radix tree routing table diagrams include inner nodes, e.g., inner node 102, and leaf nodes, e.g., leaf node 120. Inner node 102 is the root node and has a value of 31, which represents the most significant bit of the 32-bit key. In other words, the bit positions represented at each leaf node are numbered 31 (most significant) to 0 (least significant). Distinct routing tables are maintained for each logical network even when a first logical network, such as logical network 1, and a second logical network, such as logical network 3, are in the same physical location and their routing tables contain redundant search values, such as the value 10.1.0.0 at leaf node 120 and leaf node 142. For example, when traffic is received at a node in the form of a first packet with a logical traffic identifier that corresponds to logical network 1, the routing table that corresponds to the radix tree routing table diagram 100A is used to perform a route lookup. When traffic is received at the node in the form of a second packet with a logical traffic identifier that corresponds to logical network 3, the routing table that corresponds to radix tree routing diagram 100B is used to perform a route lookup. Moreover, when a search value must be removed from a routing table because, e.g., the search value is associated with a next hop to a node that is no longer in service, the search values must be removed from the radix tree structure that is associated with each different logical network, which consumes processing resources. Similarly, adding new nodes to the network will result in multiple redundant updates of the radix tree structures.
Accordingly there is a need for a technique for forwarding packet-based traffic that does not require distinct radix trees for each of a plurality of logical networks.